//
// Created by liushuai on 12/21/19.
//
#include "climbStairs4.h"
int climbStairs4(int n){
    return (pow((1+sqrt(5))/2,n+1)-pow((1-sqrt(5))/2,n+1))/sqrt(5);
//    return (3*std::sqrt(5)+5)/10*pow((1+sqrt(5)/2),n-1)+(5-3*sqrt(5))/10*(pow((1-sqrt(5))/2,n));
}
